A cache is generally a high speed memory system that stores the most recently used instructions or data from a larger, but slower, memory system. Because programs frequently use a subset of instructions or data repeatedly, the cache is a cost effective method of statistically enhancing the memory system, without having to resort to the expense of making all of the memory system faster.
In order to determine whether the requested data is stored in the cache, a comparison of the requested data address with the addresses stored in the cache is performed. For example, when a processor performs a read operation, it will first check to see if the requested data or instruction is in the cache by performing such a comparison. If, through hit detection, it is determined that the data/instruction is stored in the cache, it is considered a cache “hit,” and the cache very quickly provides to the processor without having to access slower main memory. If the data or instruction is not found in the cache, it is considered a cache “miss.” In the case of a cache miss, the processor fetches the item from main memory, and also stores a copy in the cache making it available in the cache for subsequent requests. Utilization of cache memories therefore requires some sort of comparison or “hit detection.”
In addition to detecting cache hits, it may be desirable to ensure the integrity of the data stored in the cache or tag address memory through error detection and correction techniques. For example, error correction code (ECC), sometimes referred to as “error checking and correcting,” allows accessed data to be checked for errors and, if necessary, immediately corrected. Generally, with respect to data storage, a unit of data is stored in memory, storage, cache, etc. A code corresponding to the bit sequence of the data is calculated and stored along with the data. For example, for each 64-bit word, an extra seven bits may be utilized to store the code. When the data is requested, a new code is calculated using the original algorithm for the data, and the new code is compared to the code that was originally stored with the data. If the codes match one another, the data is considered error-free. Otherwise, the missing or erroneous bits are corrected using the code comparison. An example of such an ECC is the Reed-Solomon code, which includes error detection and error correction codes based on mathematical algorithms and binary structural logic, which is thus able to detect and restore incorrect and/or missing bits.
In many prior art systems, hit detection and error detection/correction has been performed in a serial manner. Data would be read from the memory, send through the ECC circuitry, then through hit detection circuitry, and finally processed. This serial methodology is inefficient, as data is always subjected to the ECC circuitry even though no error correction is necessary a large majority of the time.
Prior art systems have also utilized multiple error correction codes, requiring additional memory capacity to house all of the ECC information. Further, these prior art systems perform a comparison of all bits, including ECC bits, which adversely affects performance.
Therefore, it would be desirable to provide a system and method for increasing computing throughput by concurrently performing data error detection/correction and cache hit detection in parallel, while reducing compare times and required memory sizes. The present invention provides a solution to these and other problems of the prior art, and offers other advantages over the prior art.